
package com.lee.tree; 
 
 
import com.lee.logger.Logger; 
import lombok.Data; 
 
import java.util.*; 
 
@Data 
public class PatternTree { 
    private TiltedTimeNode root;
 
    public PatternTree(){
        this.setRoot(new TiltedTimeNode(this,null));
    }
 
    public void add(List<String> transaction,long countValue){
 
        TiltedTimeNode point = this.getRoot();
        for(String item:transaction){
            TiltedTimeNode nextPoint = point.search(item);
 
            if (nextPoint == null){
 
                nextPoint = new TiltedTimeNode(this,item);
                point.add(nextPoint);
 
            }
            point = nextPoint;
        }
        point.setCounts(countValue);
    }
 
    public Integer inspectAndUpdate(){
 
        this.getRoot().inspectAndUpdateStack();
        return this.getRoot().getCn().stream().mapToInt(Integer::intValue).sum();
 
    }
 
 
    public void inspect(){
        Logger.info("Pattern Tree:");
        this.getRoot().inspect(1);
 
    }
 
    public void findWithSuffix(List<TwoTuple<List<String>, Long>> frequents, TiltedTimeNode treeNode,List<String> suffix){
        for(String item:treeNode.getChildren().keySet()){
            TiltedTimeNode nodes = treeNode.getChildren().get(item);
            List<String> foundSet = new ArrayList<>(suffix);
            foundSet.add(0,item);
            long countSum = nodes.getCounts().stream().mapToLong(Long::longValue).sum();
 
            List<String> reverseFoundSet = new ArrayList<>(foundSet);
            Collections.reverse(reverseFoundSet);
            frequents.add(new TwoTuple<List<String>,Long>(reverseFoundSet,countSum));
            if(nodes != null){
                findWithSuffix(frequents,nodes,foundSet);
            }
        }
    }
 
    public void findWithSuffixStack(List<TwoTuple<List<String>, Long>> frequents, TiltedTimeNode treeNode){
        //将结点入栈
        Stack<TiltedTimeNode> stack = new Stack<>();
        Stack<List<String>> suffixStack = new Stack<>();
        for(String item:treeNode.getChildren().keySet()) {
            TiltedTimeNode child = treeNode.getChildren().get(item);
 
 
            stack.push(child);
            suffixStack.push(new ArrayList<>());
        }
 
        while(!stack.empty()){
 
            //遍历结点
            TiltedTimeNode node = stack.pop();
            List<String> suffix = suffixStack.pop();
            List<String> foundSet = new ArrayList<>(suffix);
 
            foundSet.add(0, node.getItem());
            long countSum = node.getCounts().stream().mapToLong(Long::longValue).sum();
            if(countSum == 0){
                Logger.info("zero",node.getItem(),node);
            }
            List<String> reverseFoundSet = new ArrayList<>(foundSet);
            Collections.reverse(reverseFoundSet);
            frequents.add(new TwoTuple<List<String>, Long>(reverseFoundSet, countSum));
            //将该结点的孩子结点都放到栈里面
            for(String item:node.getChildren().keySet()){
 
 
                TiltedTimeNode child = node.getChildren().get(item);
 
 
                if(child != null){
                    //将结点入栈
                    stack.push(child);
                    suffixStack.push(foundSet);
                }
            }
 
 
        }
    }
    //深度优先搜索
    public List<TwoTuple<List<String>, Long>> getFrequents(){
        TiltedTimeNode master = this.getRoot();
        List<TwoTuple<List<String>, Long>> frequents = new ArrayList<>();
 
        findWithSuffixStack(frequents,master);
//        findWithSuffix(frequents,master,new ArrayList<>());
 
 
 
        return frequents;
    }
 
 
    @Override
    public String toString() {
        return "FPTree{}";
    }
} 
